A common method of encrypting a plaintext message starts by substituting integers for plaintext characters according to some standard alphabet such as ITA2, ITA5, ASCII, or EBCDIC. These integers are then written in binary form to create a first string, or sequence, of 0's and 1's. To the first string is modulo 2-added another, second sequence of 0's and 1's to produce still a third sequence of 0's and 1's. The third sequence of 0's and 1's is transmitted as the encrypted message. The sender's object if to make this third string of 0's and 1's appear to be a random sequence of digits in binary form the intended receiver modulo 2-adds the second sequence to the third sequence to recover the first sequence. Thereafter, the original plaintext message is derived from the standard alphabet that was used, e.g., ITA2, ITA5, ASCII, or EBCDIC. If the second sequence is truly random, an interceptor-attacker will be unable to reproduce the first sequence. Thus, the plaintext message is preserved.
There are a number of problems with this scheme: First, random number strings are a relatively scarce commodity. Second, the receiver must have at hand exactly the same random number sequence the sender used or must be able to reproduce it. Having at hand exactly the same random number sequence the sender used requires the sharing of an enormous amount of key material. The sharing of an enormous amount of key material is impractical. Reproducing exactly the same random number sequence the sender used is impossible.
To avoid these two difficulties, a pseudo-random number generator is commonly employed by both sender and receiver. A pseudo-random number generator is a deterministic machine which, when initialized by a "seed" number, produces a string of digits which appears to be random (by passing various statistical tests). The output of a pseudo-random number generator is periodic, but the period can be made very long. When sender and receiver use pseudo-random number generators to produce the second, key, or encrypting sequence, they start with a common initializing "seed" and synchronize the outputs of their generators. Starting with a common initializing "seed" and synchronizing the outputs of the generators allows a known-plaintext attack in which an interceptor-attacker gains access to plaintext (hence to its binary digit string equivalent in terms of some standard numerical alphabet) and to the corresponding ciphertext. Knowing the digits of the binary plaintext string enables the attacker to reproduce the corresponding pseudo-random number sequence. This frequently allows the attacker to determine the algorithm, initializing "seed," and output sequence of the system's pseudo-random number generator, thus "breaking" the code.
Gaining access to plaintext and to the corresponding ciphertext as described above, with its defects, is the intended use of the pseudo-random number generator described in U.S. Pat. No. 2,949,501. U.S. Pat. No. 3,911,216 reveals a well known non-linear shift register for the same purpose. Further, U.S. Pat. No. 4,202,051 describes linear shift register used with a non-linear function to generate a pseudo-random second sequence for use in the encrypting process as previously described.
U.S. Pat. No. 4,341,925 describes an encryption process in which the signals of two pseudo-random number generators are modulo 2-added, and then the resultant sum is modulo 2-added to a binary digitalized plaintext stream prior to transmission. One of the two original pseudo-random number sequences is multiplexed with the encrypted data stream and transmitted as a synchronizing signal. Modulo 2-adding the two pseudo-random sequences increases the period of the resultant sequence, and provision is made for sender-receiver synchronized changes in the two component streams sufficiently often to avoid revealing the period of their combined output. Since this is just an enhanced pseudo-random-number stream-modulo 2-added-to-the-plaintext scheme, it will be evident that it does not bear on the present invention.
U.S. Pat. No. 4,369,434 pertains to modification of existing proprietary encryption machines which require a secret primary code known to both sender and receiver, a transmitted synchronizing signal and a randomly generated auxiliary code which is transmitted in clear. The choice of initializing secret primary code is randomly made and its address, in a memory commonly held by sender and receiver, is transmitted in clear. The secret primary codes are functionally short and subsequently changed by a predetermined secret scheme.
The system described in U.S. Pat. No. 4,369,434 superficially resembles that of the present invention in that the starting address for the first secret primary code is transmitted, as is the initializing integer of the "masking tape" in the present invention. In the system described in U.S. Pat. No. 4,369,434, however, the primary codes must be changed if the message is lengthy. In the present invention, the masking tape simply continues to run for both sender and receiver. Further, the present invention requires neither transmission of a synchronizing signal nor transmission of an auxiliary code. In short, the encrypting-decrypting algorithm described in U.S. Pat. No. 4,369,434 is different from that of the present invention.
U.S. Pat. No. 4,638,120 describes a digitalized data encryption scheme in which a time-variable random number sequence, E, is generated by the sender and transmitted to the receiver. Sender and receiver share a secret code, S, and a set of identification codes, I.sub.n, one of which is associated with each message M. To encrypt a message, the sender forms the concatenated binary sequence EI.sub.n, call it R.sub.1. An intermediate sequence, S.sub.1, is formed by adding R.sub.1 and S modulo 2, S.sub.1 =R.sub.1 .sym.S, where S is a secret code shared by sender receiver. Finally, an intrinsic code, R, is formed by ordinarily multiplication of the integers S, S.sub.1 and R.sub.1 and reducing the product modulo (2.sup.64 -1). R=S.times.S.sub.1 .times.R.sub.1 (mod (2.sup.64 -1)). Since the address of I.sub.n is transmitted to the receiver, the receiver can reconstruct the intrinsic code R. The message, as a binary bit sequence, is added modulo 2 to the intrinsic key R in binary representation. The result is the message encryption. To decrypt, the binary sequence R is modulo 2-added to the transmission. For effective communication, sender and receiver share a secret code, S, and a commonly indexed set of message identification codes. Required to be transmitted are: the encrypted message, the time variable random (or pseudo-random) digit sequence, a synchronization signal and an address for the identification code. The process described in U.S. Pat. No. 4,638,120 has no material relationship with the encrypting-decrypting algorithm or shared information of the present invention.
U.S. Pat. No. 4,791,669 pertains to a method for error reduction in the encryption of a randomized digital encrypting string, Y, added modulo 2 to a digitalized plaintext stream. To shorten lengths of garbled portions of a ciphertext string, the message is broken into chunks or "frames" with a new construction of the sequence of binary encryption bits, Y, in each frame. To do this, bits from previous frames are used to call, randomly, out of memory sequences of bits for Y. Identical machinery and memories at the receiver likewise produce successive chunks of Y and permit decryption by modulo 2 addition of Y to the ciphertext stream. It should be remarked that complicating the construction of Y increases the probability that equipment error at either sender or receiver will degrade individual framed portions of the transmission. This may even increase message degradation overall. The randomizing of the encrypting string Y differs from that of the present invention in that it requires periodic reference to memories which contain stored integers at specific addresses instead of a memory which is simply a string of pseudo-randomly selected digits as in the present invention. Moreover, synchronizing signal transmissions are required in the system of the patent, but not in that of the present invention. Finally, and perhaps most importantly, the act of encryption as described in U.S. Pat. No. 4,791,669 involves the familiar addition modulo 2 of randomized bit string, Y, and digitalized, unencrypted plaintext. As remarked above, this invites known plaintext attacks.
The following four patents, although included for completeness, have no bearing on the present invention. U.S. Pat. No. 4,206,315 reveals a method of verifying signatures appended to a digitalized message transmission. The signing process requires transmission of successive compressed encodings of successive validation tables and the existence of an independent verifier. Specific cryptosystems are irrelevant except as they are required to fit into the construction of validation tables. Hence, there is no necessary connection between the art revealed in U.S. Pat. No. 4,206,315 and that of the present invention. U.S. Pat. No. 4,326,098 describes the use of a "vault," or verifying structure, through which users of terminals in a computer network exchange encrypted messages, thus providing for authentication by a neutral part of the network. Step coding and the Data Encryption Standard are employed for encryption, although, presumably, other cryptographic schemes could also be used. Since U.S. Pat. No. 4,326,098 does not reveal any new cryptosystems as such, it also does not suggest or disclose the present invention. U.S. Pat. No. 4,418,275 pertains to a method of and apparatus for having keys to a data file, as stated therein: "In computerized processing of data it is common practice to store like data items as multiple entries within a named data file." "A portion of each record, referred to as the kay, is used to reference a specific record." "Fundamental to the processing of the data file is the search for a data record associated with a specific key. A number of techniques have been developed which perform this specific function. A class of these techniques is referred to as hashing access methods." "A hashing access method is commonly used when the number of actual keys is a small percentage of the total number of possible keys." The scheme of U.S. Pat. No. 4,418,275 is claimed to be an improved hashing access method. U.S. Pat. No. 4,418,275 has nothing to do with data encryption or rendering stored data secure. Hence, it has nothing to do with the present invention. U.S. Pat. No. 4,667,301 involves a method of generating pseudo-random numbers. U.S. Pat. No. 4,667,301 has no connection with encryption-decryption of data (except as one might wish to employ this pseudo-random number generator); hence, it has no connection with the present invention.